/**
 *	8.皇后是国际象棋中威力最大的棋子，在下面所示的棋盘上，皇后可以攻击位于箭头所覆盖位置的所有棋子。
 *	我们能不能把8个皇后放在棋盘上，它们中任何一个都无法攻击其余的皇后？这个问题被称为八皇后问题，你的任务是编写一个程序，
 *	找到八皇后问题的所有答案，看看一共有多少种答案。
 *
 *	提示：如果你采用一种叫做回溯法的技巧，就很容易编写出这个程序，编写一个函数，把皇后放在某行的第一列，
 *	然后检查它是否与棋盘上的其他皇后互相攻击，如果存在互相攻击，函数把皇后移到该行的第二列再进行检查，
 *	如果每列都存在互相攻击的情况，函数就应该返回，但是如果皇后可以放在这个位置，函数接着应该递归的调用自身，
 *	把一个皇后放在下一行，当递归调用返回时，函数再把原先那个皇后移到下一列。当一个皇后成功的放置于最后一行时，
 *	函数应该打印出棋盘，显示8个皇后的位置。
**/

#include <stdio.h>

int board[8][8];

// 打印解决方案
void print_board()
{
	int row;
	int col;
	static int n_solutions;

	n_solutions += 1;
	printf("Solution #%d:\n", n_solutions);

	for(row = 0; row < 8; row++)
	{
		for(col = 0; col < 8; col++)
		{
			if(board[row][col])
				printf("Q");
			else
				printf("+");
		}
		printf("\n");
	}
	printf("\n");
}

// 检测 board[row][col] 的上半部分的方向上是否有其他皇后
int conflicts(int row, int col)
{
	int i;
	for(i = 1; i < 8; i++)
	{
		if(row - i >= 0 && board[row - i][col])
			return 1;
//		if(col - i >= 0 && board[row][col - i])
//			return 1;
//		if(col + i < 8 && board[row][col + i])
//			return 1;
		
		if(row - i >= 0 && col - i >= 0 && board[row - i][col - i])
			return 1;
		if(row - i >= 0 && col + i < 8 && board[row - i][col + i])
			return 1;
	}
	return 0;
}

// 回溯法调用自身
void place_queen(int row)
{
	int col;
	for(col = 0; col < 8; col++)
	{
		board[row][col] = 1;
		if(row == 0 || !conflicts(row, col))
			if(row < 7)
				place_queen(row + 1);
			else
				print_board();
		board[row][col] = 0;
	}
}

int main()
{
	place_queen(0);
	return 0;
}
